#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

const int N=1e6+7;

inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

int n,m;
int a[N];
int d[N];
struct node{
	int l,r,id,ans;
}q[N];

bool cmp1(node a,node b){
	return a.l/1000==b.l/1000?a.r<b.r:a.l<b.l;
}

bool cmp3(node a,node b){
	return a.id<b.id;
}

void solve(){
	int cnt=0;
	for(int i=q[1].l;i<=q[1].r;i++){
		cnt+=d[a[i]]==0?1:0;
		d[a[i]]++;
	}
	q[1].ans=cnt;
	int l=q[1].l,r=q[1].r;
	for(int i=2;i<=m;i++){
		//printf("%d %d -- %d %d\n",l,q[i].l,r,q[i].r);
		if(q[i].l==l);
		else if(q[i].l<l){
			for(int j=l-1;j>=q[i].l;j--){
				cnt+=(d[a[j]]==0?1:0);
				d[a[j]]++;
			}
		} else {
			for(int j=l;j<q[i].l;j++){
				d[a[j]]--;
				cnt-=(d[a[j]]==0?1:0);
			}	
		}
		if(q[i].r==r);
		else if(r>q[i].r){
			for(int j=r;j>q[i].r;j--){
				d[a[j]]--;
				cnt-=(d[a[j]]==0?1:0);
			}
		} else {
			for(int j=r+1;j<=q[i].r;j++){
				cnt+=(d[a[j]]==0?1:0);
				d[a[j]]++;
			}
		}
		q[i].ans=cnt;
		l=q[i].l;
		r=q[i].r;
	}
}

int main(){
	n=read();
	for(int i=1;i<=n;i++)a[i]=read();
	m=read();
	for(int i=1;i<=m;i++){
		q[i].l=read(),q[i].r=read(),q[i].id=i;
	}
	sort(q+1,q+m+1,cmp1);
	solve();
	sort(q+1,q+m+1,cmp3);
	for(int i=1;i<=m;i++){
		printf("%d\n",q[i].ans);
	}
}

